package leetcode_100;

import java.util.Stack;

public class LongestValidParentheses_32 {

	public static void main(String[] args) {
		LongestValidParentheses_32 test=new LongestValidParentheses_32();
		System.out.println(test.longestValidParentheses1("()(()()"));

	}
	
	/**
	 * describe:动态规划 AC 50%
	 * 2018年12月23日 下午3:13:46
	 */
	public int longestValidParentheses1(String s) {
		int max=0;
		char []chars=s.toCharArray();
		int []dp=new int[chars.length];
		for(int i=1;i<chars.length;++i) {
			if(chars[i]==')') {
				if(chars[i-1]=='(')//与左边匹配了
					dp[i]=(i>=2?dp[i-2]:0)+2;
				else if(i-dp[i-1]>0&&chars[i-dp[i-1]-1]=='(')//与这个匹配
					dp[i]=dp[i-1]+((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
				max=Math.max(max, dp[i]);
			}
		}
		return max;
	}
	

	/**
	 * describe:用栈 AC 23%
	 * 2018年12月23日 下午2:56:10
	 */
	public int longestValidParentheses(String s) {
		Stack<Integer> stack = new Stack<Integer>();
		int max=0;
		char []chars=s.toCharArray();
		for(int i=0;i<chars.length;++i) {
			if(chars[i]==')'&&!stack.isEmpty()&&chars[stack.peek()]=='(') {
				stack.pop();
				max=Math.max(max, i-(stack.isEmpty()?-1:stack.peek()));
			}
			else
				stack.push(i);
		}
		return max;
	}


}
